package com.xsherl.leetcode.solution;

import java.util.HashMap;
import java.util.LinkedList;

public class MinimumWindowSubstring {

    /**
     * 滑动窗口
     * 运用hash表存储t中字母出现次数
     * 然后遍历s的字符，如果在t中出现过，就减去次数并存储字符和当前索引到队列中
     * 如果发现t中字符完全出现，则记录当前子串长度，最终返回长度最小的子串
     */
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> charCount = new HashMap<>();
        for (int j = 0; j < t.length(); ++j){
            char key = t.charAt(j);
            int count = charCount.getOrDefault(key, 0);
            charCount.put(key, count + 1);
        }
        int patternLen = t.length();
        LinkedList<Integer> indexes = new LinkedList<>();
        LinkedList<Character> chars = new LinkedList<>();
        int min = s.length() + 1, index = 0;
        for (int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if (charCount.containsKey(c)){
                indexes.offer(i);
                chars.offer(c);
                int count = charCount.get(c);
                charCount.put(c,  count - 1);
                if (count > 0){
                    patternLen--;
                }
                while (patternLen == 0){
                    char leftChar = chars.poll();
                    int left = indexes.poll();
                    int len = i - left + 1;
                    if (min > len){
                        min = len;
                        index = left;
                    }
                    int leftCount = charCount.get(leftChar);
                    charCount.put(leftChar, leftCount + 1);
                    if (leftCount >= 0){
                        patternLen++;
                    }
                }
            }
        }
        if (min == s.length() + 1){
            return "";
        }
        return s.substring(index, index + min);
    }

    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";
        String s1 = new MinimumWindowSubstring().minWindow(s, t);
        System.out.println(s1);
//        Assert.isTrue("cwae".equals(s1));
    }
}
